#include "software_renderer.h"

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

#include "triangulation.h"

using namespace std;

namespace CMU462 {


// Implements SoftwareRenderer //

void SoftwareRendererImp::draw_svg( SVG& svg ) {

  // set top level transformation
  transformation = svg_2_screen;

  if (!this->render_target) return;
  this->sample_h = this->target_h * this->sample_rate;
  this->sample_w = this->target_w * this->sample_rate;
  this->sample_buffer.assign(this->sample_h * this->sample_w, Color(1, 1, 1, 1));

  // draw all elements
  for ( size_t i = 0; i < svg.elements.size(); ++i ) {
    draw_element(svg.elements[i]);
  }

  // draw canvas outline
  Vector2D a = transform(Vector2D(    0    ,     0    )); a.x--; a.y--;
  Vector2D b = transform(Vector2D(svg.width,     0    )); b.x++; b.y--;
  Vector2D c = transform(Vector2D(    0    ,svg.height)); c.x--; c.y++;
  Vector2D d = transform(Vector2D(svg.width,svg.height)); d.x++; d.y++;

  rasterize_line(a.x, a.y, b.x, b.y, Color::Black);
  rasterize_line(a.x, a.y, c.x, c.y, Color::Black);
  rasterize_line(d.x, d.y, b.x, b.y, Color::Black);
  rasterize_line(d.x, d.y, c.x, c.y, Color::Black);

  // resolve and send to render target
  resolve();

}

void SoftwareRendererImp::set_sample_rate( size_t sample_rate ) {

  // Task 4: 
  // You may want to modify this for supersampling support
  this->sample_rate = sample_rate;

  // Update sample buffere
  if (!this->render_target) 
    return;

  this->sample_h = this->target_h * this->sample_rate;
  this->sample_w = this->target_w * this->sample_rate;
  this->sample_buffer.assign(this->sample_h * this->sample_w, Color(1, 1, 1, 1));
}

void SoftwareRendererImp::set_render_target( unsigned char* render_target,
                                             size_t width, size_t height ) {

  // Task 4: 
  // You may want to modify this for supersampling support
  this->render_target = render_target;
  this->target_w = width;
  this->target_h = height;

  // Update sample buffere
  if (!this->render_target) 
    return;

  this->sample_h = this->target_h * this->sample_rate;
  this->sample_w = this->target_w * this->sample_rate;
  this->sample_buffer.assign(this->sample_h * this->sample_w, Color(1, 1, 1, 1));
}

void SoftwareRendererImp::draw_element( SVGElement* element ) {

  // Task 5 (part 1):
  // Modify this to implement the transformation stack

  switch(element->type) {
    case POINT:
      draw_point(static_cast<Point&>(*element));
      break;
    case LINE:
      draw_line(static_cast<Line&>(*element));
      break;
    case POLYLINE:
      draw_polyline(static_cast<Polyline&>(*element));
      break;
    case RECT:
      draw_rect(static_cast<Rect&>(*element));
      break;
    case POLYGON:
      draw_polygon(static_cast<Polygon&>(*element));
      break;
    case ELLIPSE:
      draw_ellipse(static_cast<Ellipse&>(*element));
      break;
    case IMAGE:
      draw_image(static_cast<Image&>(*element));
      break;
    case GROUP:
      draw_group(static_cast<Group&>(*element));
      break;
    default:
      break;
  }

}


// Primitive Drawing //

void SoftwareRendererImp::draw_point( Point& point ) {

  Vector2D p = transform(point.position);
  rasterize_point( p.x, p.y, point.style.fillColor );

}

void SoftwareRendererImp::draw_line( Line& line ) { 

  Vector2D p0 = transform(line.from);
  Vector2D p1 = transform(line.to);
  rasterize_line( p0.x, p0.y, p1.x, p1.y, line.style.strokeColor );

}

void SoftwareRendererImp::draw_polyline( Polyline& polyline ) {

  Color c = polyline.style.strokeColor;

  if( c.a != 0 ) {
    int nPoints = polyline.points.size();
    for( int i = 0; i < nPoints - 1; i++ ) {
      Vector2D p0 = transform(polyline.points[(i+0) % nPoints]);
      Vector2D p1 = transform(polyline.points[(i+1) % nPoints]);
      rasterize_line( p0.x, p0.y, p1.x, p1.y, c );
    }
  }
}

void SoftwareRendererImp::draw_rect( Rect& rect ) {

  Color c;
  
  // draw as two triangles
  float x = rect.position.x;
  float y = rect.position.y;
  float w = rect.dimension.x;
  float h = rect.dimension.y;

  Vector2D p0 = transform(Vector2D(   x   ,   y   ));
  Vector2D p1 = transform(Vector2D( x + w ,   y   ));
  Vector2D p2 = transform(Vector2D(   x   , y + h ));
  Vector2D p3 = transform(Vector2D( x + w , y + h ));
  
  // draw fill
  c = rect.style.fillColor;
  if (c.a != 0 ) {
    rasterize_triangle( p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, c );
    rasterize_triangle( p2.x, p2.y, p1.x, p1.y, p3.x, p3.y, c );
  }

  // draw outline
  c = rect.style.strokeColor;
  if( c.a != 0 ) {
    rasterize_line( p0.x, p0.y, p1.x, p1.y, c );
    rasterize_line( p1.x, p1.y, p3.x, p3.y, c );
    rasterize_line( p3.x, p3.y, p2.x, p2.y, c );
    rasterize_line( p2.x, p2.y, p0.x, p0.y, c );
  }

}

void SoftwareRendererImp::draw_polygon( Polygon& polygon ) {

  Color c;

  // draw fill
  c = polygon.style.fillColor;
  if( c.a != 0 ) {

    // triangulate
    vector<Vector2D> triangles;
    triangulate( polygon, triangles );

    // draw as triangles
    for (size_t i = 0; i < triangles.size(); i += 3) {
      Vector2D p0 = transform(triangles[i + 0]);
      Vector2D p1 = transform(triangles[i + 1]);
      Vector2D p2 = transform(triangles[i + 2]);
      rasterize_triangle( p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, c );
    }
  }

  // draw outline
  c = polygon.style.strokeColor;
  if( c.a != 0 ) {
    int nPoints = polygon.points.size();
    for( int i = 0; i < nPoints; i++ ) {
      Vector2D p0 = transform(polygon.points[(i+0) % nPoints]);
      Vector2D p1 = transform(polygon.points[(i+1) % nPoints]);
      rasterize_line( p0.x, p0.y, p1.x, p1.y, c );
    }
  }
}

void SoftwareRendererImp::draw_ellipse( Ellipse& ellipse ) {

  // Extra credit 

}

void SoftwareRendererImp::draw_image( Image& image ) {

  Vector2D p0 = transform(image.position);
  Vector2D p1 = transform(image.position + image.dimension);

  rasterize_image( p0.x, p0.y, p1.x, p1.y, image.tex );
}

void SoftwareRendererImp::draw_group( Group& group ) {

  for ( size_t i = 0; i < group.elements.size(); ++i ) {
    draw_element(group.elements[i]);
  }

}

// Rasterization //

// The input arguments in the rasterization functions 
// below are all defined in screen space coordinates

void SoftwareRendererImp::rasterize_point( float x, float y, Color color ) {

  // fill in the nearest pixel
  int sx = (int) floor(x);
  int sy = (int) floor(y);

  // check bounds
  if ( sx < 0 || sx >= target_w ) return;
  if ( sy < 0 || sy >= target_h ) return;

  // fill sample - NOT doing alpha blending!
  // every element has 4 channels -- r, g, b, a
  render_target[4 * (sx + sy * target_w)    ] = (uint8_t) (color.r * 255);
  render_target[4 * (sx + sy * target_w) + 1] = (uint8_t) (color.g * 255);
  render_target[4 * (sx + sy * target_w) + 2] = (uint8_t) (color.b * 255);
  render_target[4 * (sx + sy * target_w) + 3] = (uint8_t) (color.a * 255);

  fill_sample(sx, sy, color);
}

void SoftwareRendererImp::rasterize_line( float x0, float y0,
                                          float x1, float y1,
                                          Color color) {
  // Task 2: 
  // Implement line rasterization

  /* Bresenham Line-Drawing Algorithm */

  // // Make sure x0 < x1
  // if (x0 > x1) {
  //   // swap x0 and x1
  //   float temp_x = x0;
  //   x0 = x1;
  //   x1 = temp_x;
  //   // swap y0 and y1
  //   float temp_y = y0;
  //   y0 = y1;
  //   y1 = temp_y;
  // }

  // int sx0 = (int)floor(x0);
  // int sy0 = (int)floor(y0);
  // int sx1 = (int)floor(x1);
  // int sy1 = (int)floor(y1);

  // // Check bounds
  // if (sx0 < 0 || sx0 >= target_w || sy0 < 0 || sy0 >= target_h ||
  //     sx1 < 0 || sx1 >= target_w || sy1 < 0 || sy1 >= target_h) {
  //     return;
  // }

  // int dx = abs(sx1 - sx0);
  // int dy = abs(sy1 - sy0);
  // int x_step = (sx0 < sx1) ? 1 : -1;
  // int y_step = (sy0 < sy1) ? 1 : -1;

  // int x = sx0;
  // int y = sy0;
  // int err = dx - dy;

  // while (true) {
  //   // Fill sample - NOT doing alpha blending!
  //   rasterize_point(x, y, color);

  //   // The end of the line
  //   if (x == sx1 && y == sy1) {
  //     break;
  //   }

  //   // Use err to choose the point
  //   int e = err << 1;
  //   if (e > -dy) {
  //     err -= dy;
  //     x += x_step;
  //   }
  //   if (e < dx) {
  //     err += dx;
  //     y += y_step;
  //   }
  // }

  /* Xiaolin Wu's Line-Drawing Algorithm */

  // Define inline functions, otherwises it is easy to make mistakes
  auto ipart = [](float x) -> int { return static_cast<int>(floor(x)); };
  auto round = [ipart](float x) -> int { return ipart(x + 0.5); };
  auto fpart = [](float x) -> float { return x - floor(x); };
  auto rfpart = [fpart](float x) -> float { return 1.0 - fpart(x); };

  bool steep = abs(y1 - y0) > abs(x1 - x0);
  if (steep) {
    // Swap x0 and y0
    float temp = x0;
    x0 = y0;
    y0 = temp;
    // Swap x1 and y1
    temp = x1;
    x1 = y1;
    y1 = temp;
  }

  if (x0 > x1) {
    // Swap x0 and x1
    float temp = x0;
    x0 = x1;
    x1 = temp;
    // Swap y0 and y1
    temp = y0;
    y0 = y1;
    y1 = temp;
  }

  float dx = x1 - x0;
  float dy = y1 - y0;
  float gradient = (dx == 0.0 ? 1.0 : dy / dx);

  // Handle the first endpoint
  int xend = round(x0);
  float yend = y0 + gradient * (xend - x0);
  float xgap = rfpart(x0 + 0.5);
  int xpxl1 = xend;
  int ypxl1 = ipart(yend);

  if (steep) {
    rasterize_point(ypxl1, xpxl1, color * (rfpart(yend) * xgap));
    rasterize_point(ypxl1 + 1, xpxl1, color * (fpart(yend) * xgap));
  } 
  else {
    rasterize_point(xpxl1, ypxl1, color * (rfpart(yend) * xgap));
    rasterize_point(xpxl1, ypxl1 + 1, color * (fpart(yend) * xgap));
  }

  float intery = yend + gradient;

  // Handle the second endpoint
  xend = round(x1);
  yend = y1 + gradient * (xend - x1);
  xgap = fpart(x1 + 0.5);
  int xpxl2 = xend;
  int ypxl2 = ipart(yend);

  if (steep) {
    rasterize_point(ypxl2, xpxl2, color * (rfpart(yend) * xgap));
    rasterize_point(ypxl2 + 1, xpxl2, color * (fpart(yend) * xgap));
  } 
  else {
    rasterize_point(xpxl2, ypxl2, color * (rfpart(yend) * xgap));
    rasterize_point(xpxl2, ypxl2 + 1, color * (fpart(yend) * xgap));
  }

  // Main loop
  if (steep) {
    for (int x = xpxl1 + 1; x < xpxl2; ++x) {
      rasterize_point(ipart(intery), x, color * rfpart(intery));
      rasterize_point(ipart(intery) + 1, x, color * fpart(intery));
      intery += gradient;
    }
  } 
  else {
    for (int x = xpxl1 + 1; x < xpxl2; ++x) {
      rasterize_point(x, ipart(intery), color * rfpart(intery));
      rasterize_point(x, ipart(intery) + 1, color * fpart(intery));
      intery += gradient;
    }
  }
}

void SoftwareRendererImp::rasterize_triangle( float x0, float y0,
                                              float x1, float y1,
                                              float x2, float y2,
                                              Color color ) {
  // Task 3: 
  // Implement triangle rasterization

  /* Vector Calculation Method */

  // Get max and min of three float
  auto max = [](float a, float b, float c) -> float {
    float maxVal = a;
    if (b > maxVal) maxVal = b;
    if (c > maxVal) maxVal = c;
    return maxVal;
  };
  auto min = [](float a, float b, float c) -> float {
    float minVal = a;
    if (b < minVal) minVal = b;
    if (c < minVal) minVal = c;
    return minVal;
  };

  // Calculate the trangle bounding box
  int max_x = (int)ceil(max(x0, x1, x2));
  int max_y = (int)ceil(max(y0, y1, y2));  // Round up
  int min_x = (int)floor(min(x0, x1, x2));
  int min_y = (int)floor(min(y0, y1, y2)); // Round down

  // Iterate every pixel inside the bounding box
  for (int y = min_y; y <= max_y; ++y) {
    for (int x = min_x; x <= max_x; ++x) {
      // Points of pixel and triangle vertices
      Vector2D p(x, y);
      Vector2D p0(x0, y0);
      Vector2D p1(x1, y1);
      Vector2D p2(x2, y2);

      // Edges of triangle
      Vector2D e0 = p1 - p0;
      Vector2D e1 = p2 - p1;
      Vector2D e2 = p0 - p2;

      // Normal vector
      Vector2D n0 = Vector2D(-e0.y, e0.x);
      Vector2D n1 = Vector2D(-e1.y, e1.x);
      Vector2D n2 = Vector2D(-e2.y, e2.x);

      // Edges from triangle vertices to the pixel
      Vector2D v0 = p - p0;
      Vector2D v1 = p - p1;
      Vector2D v2 = p - p2;

      // Calculate dot products by 
      float dot0 = n0.x * v0.x + n0.y * v0.y;
      float dot1 = n1.x * v1.x + n1.y * v1.y;
      float dot2 = n2.x * v2.x + n2.y * v2.y;

      // Check if the pixel is inside the triangle using the dot products
      bool inside = (dot0 >= 0 && dot1 >= 0 && dot2 >= 0) || (dot0 <= 0 && dot1 <= 0 && dot2 <= 0);

      if (inside) {
        // Fill the pixel, half integer ??????
        rasterize_point(x+0.5, y+0.5, color);
      }
    }
  }

  /* Incremental Traversal Method */

  // // Make sure y0 <= y1 <= y2
  // if (y0 > y1) {
  //   // Find that use std::swap is more convenient
  //   swap(x0, x1);
  //   swap(y0, y1);
  // }
  // if (y0 > y2) {
  //   swap(x0, x2);
  //   swap(y0, y2);
  // }
  // if (y1 > y2) {
  //   swap(x1, x2);
  //   swap(y1, y2);
  // }

  // // Calculate 1/slopes of the edges, which are the update step of x_es
  // float dx01 = (x1 - x0) / (y1 - y0);
  // float dx02 = (x2 - x0) / (y2 - y0);
  // float dx12 = (x2 - x1) / (y2 - y1);

  // // Initialize current iterative line (only point x0 inside) x
  // float curr_x01 = x0;
  // float curr_x02 = x0;

  // // Iterate every point inside the triangle
  // for (int y = static_cast<int>(y0); y <= static_cast<int>(y2); y++) {
  //   int start_x = static_cast<int>(min(curr_x01, curr_x02));
  //   int end_x = static_cast<int>(max(curr_x01, curr_x02));

  //   // Rasterize each pixel in the scanline
  //   for (int x = start_x; x <= end_x; x++) {
  //     rasterize_point(x, y, color);
  //   }

  //   // Increment x_es fited the edge01 and edge02, which is the start and end of next scanline
  //   curr_x01 += dx01;
  //   curr_x02 += dx02;

  //   // Meet the middle point p1(x1, y1), so it is time to change to edge12
  //   if (y == static_cast<int>(y1)) {
  //     curr_x01 = x1;
  //     dx01 = dx12;
  //   }
  // }
}

void SoftwareRendererImp::rasterize_image( float x0, float y0,
                                           float x1, float y1,
                                           Texture& tex ) {
  // Task 6: 
  // Implement image rasterization

}

// resolve samples to render target
void SoftwareRendererImp::resolve( void ) {

  // Task 4: 
  // Implement supersampling
  // You may also need to modify other functions marked with "Task 4".
  Color c;
  long sample_squared = sample_rate * sample_rate;
  float sample_squared_inverse = 1.0 / float(sample_squared);
  for (int sy = 0; sy < target_h; ++sy)
    for (int sx = 0; sx < target_w; ++sx) {
      c.r = c.g = c.b = c.a = 0;
      for (int i = 0; i < sample_squared; ++i) {
        c += sample_buffer[
            (sy * sample_rate + i / sample_rate) * sample_w
                + (sx * sample_rate + i % sample_rate)
        ] * sample_squared_inverse;
      }
      rasterize_point(sx, sy, c);
    }

}


} // namespace CMU462
